/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

/* ////////////////////////////////////////////////////////////////////
//
//  CvMat, CvMatND, CvSparceMat and IplImage support functions
//  (creation, deletion, copying, retrieving and setting elements etc.)
//
// */

#include "precomp.hpp"


static struct {
    Cv_iplCreateImageHeader  createHeader;
    Cv_iplAllocateImageData  allocateData;
    Cv_iplDeallocate  deallocate;
    Cv_iplCreateROI  createROI;
    Cv_iplCloneImage  cloneImage;
}
CvIPL;

// Makes the library use native IPL image allocators
CV_IMPL void
cvSetIPLAllocators(Cv_iplCreateImageHeader createHeader,
                   Cv_iplAllocateImageData allocateData,
                   Cv_iplDeallocate deallocate,
                   Cv_iplCreateROI createROI,
                   Cv_iplCloneImage cloneImage) {
    int count = (createHeader != 0) + (allocateData != 0) + (deallocate != 0) +
                (createROI != 0) + (cloneImage != 0);

    if (count != 0 && count != 5)
        CV_Error(CV_StsBadArg, "Either all the pointers should be null or "
                 "they all should be non-null");

    CvIPL.createHeader = createHeader;
    CvIPL.allocateData = allocateData;
    CvIPL.deallocate = deallocate;
    CvIPL.createROI = createROI;
    CvIPL.cloneImage = cloneImage;
}


/****************************************************************************************\
*                               CvMat creation and basic operations                      *
\****************************************************************************************/

// Creates CvMat and underlying data
CV_IMPL CvMat*
cvCreateMat(int height, int width, int type) {
    CvMat* arr = cvCreateMatHeader(height, width, type);
    cvCreateData(arr);

    return arr;
}


static void icvCheckHuge(CvMat* arr) {
    if ((int64)arr->step * arr->rows > INT_MAX) {
        arr->type &= ~CV_MAT_CONT_FLAG;
    }
}

// Creates CvMat header only
CV_IMPL CvMat*
cvCreateMatHeader(int rows, int cols, int type) {
    type = CV_MAT_TYPE(type);

    if (rows <= 0 || cols <= 0) {
        CV_Error(CV_StsBadSize, "Non-positive width or height");
    }

    int min_step = CV_ELEM_SIZE(type) * cols;
    if (min_step <= 0) {
        CV_Error(CV_StsUnsupportedFormat, "Invalid matrix type");
    }

    CvMat* arr = (CvMat*)cvAlloc(sizeof(*arr));

    arr->step = min_step;
    arr->type = CV_MAT_MAGIC_VAL | type | CV_MAT_CONT_FLAG;
    arr->rows = rows;
    arr->cols = cols;
    arr->data.ptr = 0;
    arr->refcount = 0;
    arr->hdr_refcount = 1;

    icvCheckHuge(arr);
    return arr;
}


// Initializes CvMat header, allocated by the user
CV_IMPL CvMat*
cvInitMatHeader(CvMat* arr, int rows, int cols,
                int type, void* data, int step) {
    if (!arr) {
        CV_Error(CV_StsNullPtr, "");
    }

    if ((unsigned)CV_MAT_DEPTH(type) > CV_DEPTH_MAX) {
        CV_Error(CV_BadNumChannels, "");
    }

    if (rows <= 0 || cols <= 0) {
        CV_Error(CV_StsBadSize, "Non-positive cols or rows");
    }

    type = CV_MAT_TYPE(type);
    arr->type = type | CV_MAT_MAGIC_VAL;
    arr->rows = rows;
    arr->cols = cols;
    arr->data.ptr = (uchar*)data;
    arr->refcount = 0;
    arr->hdr_refcount = 0;

    int pix_size = CV_ELEM_SIZE(type);
    int min_step = arr->cols * pix_size;

    if (step != CV_AUTOSTEP && step != 0) {
        if (step < min_step) {
            CV_Error(CV_BadStep, "");
        }
        arr->step = step;
    } else {
        arr->step = min_step;
    }

    arr->type = CV_MAT_MAGIC_VAL | type |
                (arr->rows == 1 || arr->step == min_step ? CV_MAT_CONT_FLAG : 0);

    icvCheckHuge(arr);
    return arr;
}


#undef CV_IS_MAT_HDR_Z
#define CV_IS_MAT_HDR_Z(mat) \
    ((mat) != NULL && \
    (((const CvMat*)(mat))->type & CV_MAGIC_MASK) == CV_MAT_MAGIC_VAL && \
    ((const CvMat*)(mat))->cols >= 0 && ((const CvMat*)(mat))->rows >= 0)

// Deallocates the CvMat structure and underlying data
CV_IMPL void
cvReleaseMat(CvMat** array) {
    if (!array) {
        CV_Error(CV_HeaderIsNull, "");
    }

    if (*array) {
        CvMat* arr = *array;

        if (!CV_IS_MAT_HDR_Z(arr) && !CV_IS_MATND_HDR(arr)) {
            CV_Error(CV_StsBadFlag, "");
        }

        *array = 0;

        cvDecRefData(arr);
        cvFree(&arr);
    }
}


// Creates a copy of matrix
CV_IMPL CvMat*
cvCloneMat(const CvMat* src) {
    if (!CV_IS_MAT_HDR(src)) {
        CV_Error(CV_StsBadArg, "Bad CvMat header");
    }

    CvMat* dst = cvCreateMatHeader(src->rows, src->cols, src->type);

    if (src->data.ptr) {
        cvCreateData(dst);
        cvCopy(src, dst);
    }

    return dst;
}


/****************************************************************************************\
*                               CvMatND creation and basic operations                    *
\****************************************************************************************/

CV_IMPL CvMatND*
cvInitMatNDHeader(CvMatND* mat, int dims, const int* sizes,
                  int type, void* data) {
    type = CV_MAT_TYPE(type);
    int64 step = CV_ELEM_SIZE(type);

    if (!mat) {
        CV_Error(CV_StsNullPtr, "NULL matrix header pointer");
    }

    if (step == 0) {
        CV_Error(CV_StsUnsupportedFormat, "invalid array data type");
    }

    if (!sizes) {
        CV_Error(CV_StsNullPtr, "NULL <sizes> pointer");
    }

    if (dims <= 0 || dims > CV_MAX_DIM)
        CV_Error(CV_StsOutOfRange,
                 "non-positive or too large number of dimensions");

    for (int i = dims - 1; i >= 0; i--) {
        if (sizes[i] <= 0) {
            CV_Error(CV_StsBadSize, "one of dimesion sizes is non-positive");
        }
        mat->dim[i].size = sizes[i];
        if (step > INT_MAX) {
            CV_Error(CV_StsOutOfRange, "The array is too big");
        }
        mat->dim[i].step = (int)step;
        step *= sizes[i];
    }

    mat->type = CV_MATND_MAGIC_VAL | (step <= INT_MAX ? CV_MAT_CONT_FLAG : 0) | type;
    mat->dims = dims;
    mat->data.ptr = (uchar*)data;
    mat->refcount = 0;
    mat->hdr_refcount = 0;
    return mat;
}


// Creates CvMatND and underlying data
CV_IMPL CvMatND*
cvCreateMatND(int dims, const int* sizes, int type) {
    CvMatND* arr = cvCreateMatNDHeader(dims, sizes, type);
    cvCreateData(arr);

    return arr;
}


// Creates CvMatND header only
CV_IMPL CvMatND*
cvCreateMatNDHeader(int dims, const int* sizes, int type) {
    if (dims <= 0 || dims > CV_MAX_DIM)
        CV_Error(CV_StsOutOfRange,
                 "non-positive or too large number of dimensions");

    CvMatND* arr = (CvMatND*)cvAlloc(sizeof(*arr));

    cvInitMatNDHeader(arr, dims, sizes, type, 0);
    arr->hdr_refcount = 1;
    return arr;
}


// Creates a copy of nD array
CV_IMPL CvMatND*
cvCloneMatND(const CvMatND* src) {
    if (!CV_IS_MATND_HDR(src)) {
        CV_Error(CV_StsBadArg, "Bad CvMatND header");
    }

    int* sizes = (int*)cvStackAlloc(src->dims * sizeof(sizes[0]));

    for (int i = 0; i < src->dims; i++) {
        sizes[i] = src->dim[i].size;
    }

    CvMatND* dst = cvCreateMatNDHeader(src->dims, sizes, src->type);

    if (src->data.ptr) {
        cvCreateData(dst);
        cvCopy(src, dst);
    }

    return dst;
}


static CvMatND*
cvGetMatND(const CvArr* arr, CvMatND* matnd, int* coi) {
    CvMatND* result = 0;

    if (coi) {
        *coi = 0;
    }

    if (!matnd || !arr) {
        CV_Error(CV_StsNullPtr, "NULL array pointer is passed");
    }

    if (CV_IS_MATND_HDR(arr)) {
        if (!((CvMatND*)arr)->data.ptr) {
            CV_Error(CV_StsNullPtr, "The matrix has NULL data pointer");
        }

        result = (CvMatND*)arr;
    } else {
        CvMat stub, *mat = (CvMat*)arr;

        if (CV_IS_IMAGE_HDR(mat)) {
            mat = cvGetMat(mat, &stub, coi);
        }

        if (!CV_IS_MAT_HDR(mat)) {
            CV_Error(CV_StsBadArg, "Unrecognized or unsupported array type");
        }

        if (!mat->data.ptr) {
            CV_Error(CV_StsNullPtr, "Input array has NULL data pointer");
        }

        matnd->data.ptr = mat->data.ptr;
        matnd->refcount = 0;
        matnd->hdr_refcount = 0;
        matnd->type = mat->type;
        matnd->dims = 2;
        matnd->dim[0].size = mat->rows;
        matnd->dim[0].step = mat->step;
        matnd->dim[1].size = mat->cols;
        matnd->dim[1].step = CV_ELEM_SIZE(mat->type);
        result = matnd;
    }

    return result;
}


// returns number of dimensions to iterate.
/*
Checks whether <count> arrays have equal type, sizes (mask is optional array
that needs to have the same size, but 8uC1 or 8sC1 type).
Returns number of dimensions to iterate through:
0 means that all arrays are continuous,
1 means that all arrays are vectors of continuous arrays etc.
and the size of largest common continuous part of the arrays
*/
CV_IMPL int
cvInitNArrayIterator(int count, CvArr** arrs,
                     const CvArr* mask, CvMatND* stubs,
                     CvNArrayIterator* iterator, int flags) {
    int dims = -1;
    int i, j, size, dim0 = -1;
    int64 step;
    CvMatND* hdr0 = 0;

    if (count < 1 || count > CV_MAX_ARR) {
        CV_Error(CV_StsOutOfRange, "Incorrect number of arrays");
    }

    if (!arrs || !stubs) {
        CV_Error(CV_StsNullPtr, "Some of required array pointers is NULL");
    }

    if (!iterator) {
        CV_Error(CV_StsNullPtr, "Iterator pointer is NULL");
    }

    for (i = 0; i <= count; i++) {
        const CvArr* arr = i < count ? arrs[i] : mask;
        CvMatND* hdr;

        if (!arr) {
            if (i < count) {
                CV_Error(CV_StsNullPtr, "Some of required array pointers is NULL");
            }
            break;
        }

        if (CV_IS_MATND(arr)) {
            hdr = (CvMatND*)arr;
        } else {
            int coi = 0;
            hdr = cvGetMatND(arr, stubs + i, &coi);
            if (coi != 0) {
                CV_Error(CV_BadCOI, "COI set is not allowed here");
            }
        }

        iterator->hdr[i] = hdr;

        if (i > 0) {
            if (hdr->dims != hdr0->dims)
                CV_Error(CV_StsUnmatchedSizes,
                         "Number of dimensions is the same for all arrays");

            if (i < count) {
                switch (flags & (CV_NO_DEPTH_CHECK | CV_NO_CN_CHECK)) {
                case 0:
                    if (!CV_ARE_TYPES_EQ(hdr, hdr0))
                        CV_Error(CV_StsUnmatchedFormats,
                                 "Data type is not the same for all arrays");
                    break;
                case CV_NO_DEPTH_CHECK:
                    if (!CV_ARE_CNS_EQ(hdr, hdr0))
                        CV_Error(CV_StsUnmatchedFormats,
                                 "Number of channels is not the same for all arrays");
                    break;
                case CV_NO_CN_CHECK:
                    if (!CV_ARE_CNS_EQ(hdr, hdr0))
                        CV_Error(CV_StsUnmatchedFormats,
                                 "Depth is not the same for all arrays");
                    break;
                }
            } else {
                if (!CV_IS_MASK_ARR(hdr)) {
                    CV_Error(CV_StsBadMask, "Mask should have 8uC1 or 8sC1 data type");
                }
            }

            if (!(flags & CV_NO_SIZE_CHECK)) {
                for (j = 0; j < hdr->dims; j++)
                    if (hdr->dim[j].size != hdr0->dim[j].size)
                        CV_Error(CV_StsUnmatchedSizes,
                                 "Dimension sizes are the same for all arrays");
            }
        } else {
            hdr0 = hdr;
        }

        step = CV_ELEM_SIZE(hdr->type);
        for (j = hdr->dims - 1; j > dim0; j--) {
            if (step != hdr->dim[j].step) {
                break;
            }
            step *= hdr->dim[j].size;
        }

        if (j == dim0 && step > INT_MAX) {
            j++;
        }

        if (j > dim0) {
            dim0 = j;
        }

        iterator->hdr[i] = (CvMatND*)hdr;
        iterator->ptr[i] = (uchar*)hdr->data.ptr;
    }

    size = 1;
    for (j = hdr0->dims - 1; j > dim0; j--) {
        size *= hdr0->dim[j].size;
    }

    dims = dim0 + 1;
    iterator->dims = dims;
    iterator->count = count;
    iterator->size = cvSize(size, 1);

    for (i = 0; i < dims; i++) {
        iterator->stack[i] = hdr0->dim[i].size;
    }

    return dims;
}


// returns zero value if iteration is finished, non-zero otherwise
CV_IMPL int cvNextNArraySlice(CvNArrayIterator* iterator) {
    assert(iterator != 0);
    int i, dims, size = 0;

    for (dims = iterator->dims; dims > 0; dims--) {
        for (i = 0; i < iterator->count; i++) {
            iterator->ptr[i] += iterator->hdr[i]->dim[dims - 1].step;
        }

        if (--iterator->stack[dims - 1] > 0) {
            break;
        }

        size = iterator->hdr[0]->dim[dims - 1].size;

        for (i = 0; i < iterator->count; i++) {
            iterator->ptr[i] -= (size_t)size * iterator->hdr[i]->dim[dims - 1].step;
        }

        iterator->stack[dims - 1] = size;
    }

    return dims > 0;
}


/****************************************************************************************\
*                            CvSparseMat creation and basic operations                   *
\****************************************************************************************/


// Creates CvMatND and underlying data
CV_IMPL CvSparseMat*
cvCreateSparseMat(int dims, const int* sizes, int type) {
    type = CV_MAT_TYPE(type);
    int pix_size1 = CV_ELEM_SIZE1(type);
    int pix_size = pix_size1 * CV_MAT_CN(type);
    int i, size;
    CvMemStorage* storage;

    if (pix_size == 0) {
        CV_Error(CV_StsUnsupportedFormat, "invalid array data type");
    }

    if (dims <= 0 || dims > CV_MAX_DIM_HEAP) {
        CV_Error(CV_StsOutOfRange, "bad number of dimensions");
    }

    if (!sizes) {
        CV_Error(CV_StsNullPtr, "NULL <sizes> pointer");
    }

    for (i = 0; i < dims; i++) {
        if (sizes[i] <= 0) {
            CV_Error(CV_StsBadSize, "one of dimesion sizes is non-positive");
        }
    }

    CvSparseMat* arr = (CvSparseMat*)cvAlloc(sizeof(*arr) + MAX(0, dims - CV_MAX_DIM) * sizeof(arr->size[0]));

    arr->type = CV_SPARSE_MAT_MAGIC_VAL | type;
    arr->dims = dims;
    arr->refcount = 0;
    arr->hdr_refcount = 1;
    memcpy(arr->size, sizes, dims * sizeof(sizes[0]));

    arr->valoffset = (int)cvAlign(sizeof(CvSparseNode), pix_size1);
    arr->idxoffset = (int)cvAlign(arr->valoffset + pix_size, sizeof(int));
    size = (int)cvAlign(arr->idxoffset + dims * sizeof(int), sizeof(CvSetElem));

    storage = cvCreateMemStorage(CV_SPARSE_MAT_BLOCK);
    arr->heap = cvCreateSet(0, sizeof(CvSet), size, storage);

    arr->hashsize = CV_SPARSE_HASH_SIZE0;
    size = arr->hashsize * sizeof(arr->hashtable[0]);

    arr->hashtable = (void**)cvAlloc(size);
    memset(arr->hashtable, 0, size);

    return arr;
}


// Creates CvMatND and underlying data
CV_IMPL void
cvReleaseSparseMat(CvSparseMat** array) {
    if (!array) {
        CV_Error(CV_HeaderIsNull, "");
    }

    if (*array) {
        CvSparseMat* arr = *array;

        if (!CV_IS_SPARSE_MAT_HDR(arr)) {
            CV_Error(CV_StsBadFlag, "");
        }

        *array = 0;

        CvMemStorage* storage = arr->heap->storage;
        cvReleaseMemStorage(&storage);
        cvFree(&arr->hashtable);
        cvFree(&arr);
    }
}


// Creates CvMatND and underlying data
CV_IMPL CvSparseMat*
cvCloneSparseMat(const CvSparseMat* src) {
    if (!CV_IS_SPARSE_MAT_HDR(src)) {
        CV_Error(CV_StsBadArg, "Invalid sparse array header");
    }

    CvSparseMat* dst = cvCreateSparseMat(src->dims, src->size, src->type);
    cvCopy(src, dst);
    return dst;
}


CvSparseNode*
cvInitSparseMatIterator(const CvSparseMat* mat, CvSparseMatIterator* iterator) {
    CvSparseNode* node = 0;
    int idx;

    if (!CV_IS_SPARSE_MAT(mat)) {
        CV_Error(CV_StsBadArg, "Invalid sparse matrix header");
    }

    if (!iterator) {
        CV_Error(CV_StsNullPtr, "NULL iterator pointer");
    }

    iterator->mat = (CvSparseMat*)mat;
    iterator->node = 0;

    for (idx = 0; idx < mat->hashsize; idx++)
        if (mat->hashtable[idx]) {
            node = iterator->node = (CvSparseNode*)mat->hashtable[idx];
            break;
        }

    iterator->curidx = idx;
    return node;
}

#define ICV_SPARSE_MAT_HASH_MULTIPLIER  cv::SparseMat::HASH_SCALE

static uchar*
icvGetNodePtr(CvSparseMat* mat, const int* idx, int* _type,
              int create_node, unsigned* precalc_hashval) {
    uchar* ptr = 0;
    int i, tabidx;
    unsigned hashval = 0;
    CvSparseNode* node;
    assert(CV_IS_SPARSE_MAT(mat));

    if (!precalc_hashval) {
        for (i = 0; i < mat->dims; i++) {
            int t = idx[i];
            if ((unsigned)t >= (unsigned)mat->size[i]) {
                CV_Error(CV_StsOutOfRange, "One of indices is out of range");
            }
            hashval = hashval * ICV_SPARSE_MAT_HASH_MULTIPLIER + t;
        }
    } else {
        hashval = *precalc_hashval;
    }

    tabidx = hashval & (mat->hashsize - 1);
    hashval &= INT_MAX;

    if (create_node >= -1) {
        for (node = (CvSparseNode*)mat->hashtable[tabidx];
                node != 0; node = node->next) {
            if (node->hashval == hashval) {
                int* nodeidx = CV_NODE_IDX(mat, node);
                for (i = 0; i < mat->dims; i++)
                    if (idx[i] != nodeidx[i]) {
                        break;
                    }
                if (i == mat->dims) {
                    ptr = (uchar*)CV_NODE_VAL(mat, node);
                    break;
                }
            }
        }
    }

    if (!ptr && create_node) {
        if (mat->heap->active_count >= mat->hashsize * CV_SPARSE_HASH_RATIO) {
            void** newtable;
            int newsize = MAX(mat->hashsize * 2, CV_SPARSE_HASH_SIZE0);
            int newrawsize = newsize * sizeof(newtable[0]);

            CvSparseMatIterator iterator;
            assert((newsize & (newsize - 1)) == 0);

            // resize hash table
            newtable = (void**)cvAlloc(newrawsize);
            memset(newtable, 0, newrawsize);

            node = cvInitSparseMatIterator(mat, &iterator);
            while (node) {
                CvSparseNode* next = cvGetNextSparseNode(&iterator);
                int newidx = node->hashval & (newsize - 1);
                node->next = (CvSparseNode*)newtable[newidx];
                newtable[newidx] = node;
                node = next;
            }

            cvFree(&mat->hashtable);
            mat->hashtable = newtable;
            mat->hashsize = newsize;
            tabidx = hashval & (newsize - 1);
        }

        node = (CvSparseNode*)cvSetNew(mat->heap);
        node->hashval = hashval;
        node->next = (CvSparseNode*)mat->hashtable[tabidx];
        mat->hashtable[tabidx] = node;
        CV_MEMCPY_INT(CV_NODE_IDX(mat, node), idx, mat->dims);
        ptr = (uchar*)CV_NODE_VAL(mat, node);
        if (create_node > 0) {
            CV_ZERO_CHAR(ptr, CV_ELEM_SIZE(mat->type));
        }
    }

    if (_type) {
        *_type = CV_MAT_TYPE(mat->type);
    }

    return ptr;
}


static void
icvDeleteNode(CvSparseMat* mat, const int* idx, unsigned* precalc_hashval) {
    int i, tabidx;
    unsigned hashval = 0;
    CvSparseNode* node, *prev = 0;
    assert(CV_IS_SPARSE_MAT(mat));

    if (!precalc_hashval) {
        for (i = 0; i < mat->dims; i++) {
            int t = idx[i];
            if ((unsigned)t >= (unsigned)mat->size[i]) {
                CV_Error(CV_StsOutOfRange, "One of indices is out of range");
            }
            hashval = hashval * ICV_SPARSE_MAT_HASH_MULTIPLIER + t;
        }
    } else {
        hashval = *precalc_hashval;
    }

    tabidx = hashval & (mat->hashsize - 1);
    hashval &= INT_MAX;

    for (node = (CvSparseNode*)mat->hashtable[tabidx];
            node != 0; prev = node, node = node->next) {
        if (node->hashval == hashval) {
            int* nodeidx = CV_NODE_IDX(mat, node);
            for (i = 0; i < mat->dims; i++)
                if (idx[i] != nodeidx[i]) {
                    break;
                }
            if (i == mat->dims) {
                break;
            }
        }
    }

    if (node) {
        if (prev) {
            prev->next = node->next;
        } else {
            mat->hashtable[tabidx] = node->next;
        }
        cvSetRemoveByPtr(mat->heap, node);
    }
}


/****************************************************************************************\
*                          Common for multiple array types operations                    *
\****************************************************************************************/

// Allocates underlying array data
CV_IMPL void
cvCreateData(CvArr* arr) {
    if (CV_IS_MAT_HDR(arr)) {
        size_t step, total_size;
        CvMat* mat = (CvMat*)arr;
        step = mat->step;

        if (mat->data.ptr != 0) {
            CV_Error(CV_StsError, "Data is already allocated");
        }

        if (step == 0) {
            step = CV_ELEM_SIZE(mat->type) * mat->cols;
        }

        int64 _total_size = (int64)step * mat->rows + sizeof(int) + CV_MALLOC_ALIGN;
        total_size = (size_t)_total_size;
        if (_total_size != (int64)total_size) {
            CV_Error(CV_StsNoMem, "Too big buffer is allocated");
        }
        mat->refcount = (int*)cvAlloc((size_t)total_size);
        mat->data.ptr = (uchar*)cvAlignPtr(mat->refcount + 1, CV_MALLOC_ALIGN);
        *mat->refcount = 1;
    } else if (CV_IS_IMAGE_HDR(arr)) {
        IplImage* img = (IplImage*)arr;

        if (img->imageData != 0) {
            CV_Error(CV_StsError, "Data is already allocated");
        }

        if (!CvIPL.allocateData) {
            img->imageData = img->imageDataOrigin =
                                 (char*)cvAlloc((size_t)img->imageSize);
        } else {
            int depth = img->depth;
            int width = img->width;

            if (img->depth == IPL_DEPTH_32F || img->depth == IPL_DEPTH_64F) {
                img->width *= img->depth == IPL_DEPTH_32F ? sizeof(float) : sizeof(double);
                img->depth = IPL_DEPTH_8U;
            }

            CvIPL.allocateData(img, 0, 0);

            img->width = width;
            img->depth = depth;
        }
    } else if (CV_IS_MATND_HDR(arr)) {
        CvMatND* mat = (CvMatND*)arr;
        int i;
        size_t total_size = CV_ELEM_SIZE(mat->type);

        if (mat->data.ptr != 0) {
            CV_Error(CV_StsError, "Data is already allocated");
        }

        if (CV_IS_MAT_CONT(mat->type)) {
            total_size = (size_t)mat->dim[0].size * (mat->dim[0].step != 0 ?
                         mat->dim[0].step : total_size);
        } else {
            for (i = mat->dims - 1; i >= 0; i--) {
                size_t size = (size_t)mat->dim[i].step * mat->dim[i].size;

                if (total_size < size) {
                    total_size = size;
                }
            }
        }

        mat->refcount = (int*)cvAlloc(total_size +
                                      sizeof(int) + CV_MALLOC_ALIGN);
        mat->data.ptr = (uchar*)cvAlignPtr(mat->refcount + 1, CV_MALLOC_ALIGN);
        *mat->refcount = 1;
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }
}


// Assigns external data to array
CV_IMPL void
cvSetData(CvArr* arr, void* data, int step) {
    int pix_size, min_step;

    if (CV_IS_MAT_HDR(arr) || CV_IS_MATND_HDR(arr)) {
        cvReleaseData(arr);
    }

    if (CV_IS_MAT_HDR(arr)) {
        CvMat* mat = (CvMat*)arr;

        int type = CV_MAT_TYPE(mat->type);
        pix_size = CV_ELEM_SIZE(type);
        min_step = mat->cols * pix_size;

        if (step != CV_AUTOSTEP && step != 0) {
            if (step < min_step && data != 0) {
                CV_Error(CV_BadStep, "");
            }
            mat->step = step;
        } else {
            mat->step = min_step;
        }

        mat->data.ptr = (uchar*)data;
        mat->type = CV_MAT_MAGIC_VAL | type |
                    (mat->rows == 1 || mat->step == min_step ? CV_MAT_CONT_FLAG : 0);
        icvCheckHuge(mat);
    } else if (CV_IS_IMAGE_HDR(arr)) {
        IplImage* img = (IplImage*)arr;

        pix_size = ((img->depth & 255) >> 3) * img->nChannels;
        min_step = img->width * pix_size;

        if (step != CV_AUTOSTEP && img->height > 1) {
            if (step < min_step && data != 0) {
                CV_Error(CV_BadStep, "");
            }
            img->widthStep = step;
        } else {
            img->widthStep = min_step;
        }

        img->imageSize = img->widthStep * img->height;
        img->imageData = img->imageDataOrigin = (char*)data;

        if ((((int)(size_t)data | step) & 7) == 0 &&
                cvAlign(img->width * pix_size, 8) == step) {
            img->align = 8;
        } else {
            img->align = 4;
        }
    } else if (CV_IS_MATND_HDR(arr)) {
        CvMatND* mat = (CvMatND*)arr;
        int i;
        int64 cur_step;

        if (step != CV_AUTOSTEP)
            CV_Error(CV_BadStep,
                     "For multidimensional array only CV_AUTOSTEP is allowed here");

        mat->data.ptr = (uchar*)data;
        cur_step = CV_ELEM_SIZE(mat->type);

        for (i = mat->dims - 1; i >= 0; i--) {
            if (cur_step > INT_MAX) {
                CV_Error(CV_StsOutOfRange, "The array is too big");
            }
            mat->dim[i].step = (int)cur_step;
            cur_step *= mat->dim[i].size;
        }
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }
}


// Deallocates array's data
CV_IMPL void
cvReleaseData(CvArr* arr) {
    if (CV_IS_MAT_HDR(arr) || CV_IS_MATND_HDR(arr)) {
        CvMat* mat = (CvMat*)arr;
        cvDecRefData(mat);
    } else if (CV_IS_IMAGE_HDR(arr)) {
        IplImage* img = (IplImage*)arr;

        if (!CvIPL.deallocate) {
            char* ptr = img->imageDataOrigin;
            img->imageData = img->imageDataOrigin = 0;
            cvFree(&ptr);
        } else {
            CvIPL.deallocate(img, IPL_IMAGE_DATA);
        }
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }
}


// Retrieves essential information about image ROI or CvMat data
CV_IMPL void
cvGetRawData(const CvArr* arr, uchar** data, int* step, CvSize* roi_size) {
    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        if (step) {
            *step = mat->step;
        }

        if (data) {
            *data = mat->data.ptr;
        }

        if (roi_size) {
            *roi_size = cvGetMatSize(mat);
        }
    } else if (CV_IS_IMAGE(arr)) {
        IplImage* img = (IplImage*)arr;

        if (step) {
            *step = img->widthStep;
        }

        if (data) {
            *data = cvPtr2D(img, 0, 0);
        }

        if (roi_size) {
            if (img->roi) {
                *roi_size = cvSize(img->roi->width, img->roi->height);
            } else {
                *roi_size = cvSize(img->width, img->height);
            }
        }
    } else if (CV_IS_MATND(arr)) {
        CvMatND* mat = (CvMatND*)arr;

        if (!CV_IS_MAT_CONT(mat->type)) {
            CV_Error(CV_StsBadArg, "Only continuous nD arrays are supported here");
        }

        if (data) {
            *data = mat->data.ptr;
        }

        if (roi_size || step) {
            int i, size1 = mat->dim[0].size, size2 = 1;

            if (mat->dims > 2)
                for (i = 1; i < mat->dims; i++) {
                    size1 *= mat->dim[i].size;
                }
            else {
                size2 = mat->dim[1].size;
            }

            if (roi_size) {
                roi_size->width = size2;
                roi_size->height = size1;
            }

            if (step) {
                *step = mat->dim[0].step;
            }
        }
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }
}


CV_IMPL int
cvGetElemType(const CvArr* arr) {
    int type = -1;
    if (CV_IS_MAT_HDR(arr) || CV_IS_MATND_HDR(arr) || CV_IS_SPARSE_MAT_HDR(arr)) {
        type = CV_MAT_TYPE(((CvMat*)arr)->type);
    } else if (CV_IS_IMAGE(arr)) {
        IplImage* img = (IplImage*)arr;
        type = CV_MAKETYPE(IPL2CV_DEPTH(img->depth), img->nChannels);
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return type;
}


// Returns a number of array dimensions
CV_IMPL int
cvGetDims(const CvArr* arr, int* sizes) {
    int dims = -1;
    if (CV_IS_MAT_HDR(arr)) {
        CvMat* mat = (CvMat*)arr;

        dims = 2;
        if (sizes) {
            sizes[0] = mat->rows;
            sizes[1] = mat->cols;
        }
    } else if (CV_IS_IMAGE(arr)) {
        IplImage* img = (IplImage*)arr;
        dims = 2;

        if (sizes) {
            sizes[0] = img->height;
            sizes[1] = img->width;
        }
    } else if (CV_IS_MATND_HDR(arr)) {
        CvMatND* mat = (CvMatND*)arr;
        dims = mat->dims;

        if (sizes) {
            int i;
            for (i = 0; i < dims; i++) {
                sizes[i] = mat->dim[i].size;
            }
        }
    } else if (CV_IS_SPARSE_MAT_HDR(arr)) {
        CvSparseMat* mat = (CvSparseMat*)arr;
        dims = mat->dims;

        if (sizes) {
            memcpy(sizes, mat->size, dims * sizeof(sizes[0]));
        }
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return dims;
}


// Returns the size of particular array dimension
CV_IMPL int
cvGetDimSize(const CvArr* arr, int index) {
    int size = -1;

    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        switch (index) {
        case 0:
            size = mat->rows;
            break;
        case 1:
            size = mat->cols;
            break;
        default:
            CV_Error(CV_StsOutOfRange, "bad dimension index");
        }
    } else if (CV_IS_IMAGE(arr)) {
        IplImage* img = (IplImage*)arr;

        switch (index) {
        case 0:
            size = !img->roi ? img->height : img->roi->height;
            break;
        case 1:
            size = !img->roi ? img->width : img->roi->width;
            break;
        default:
            CV_Error(CV_StsOutOfRange, "bad dimension index");
        }
    } else if (CV_IS_MATND_HDR(arr)) {
        CvMatND* mat = (CvMatND*)arr;

        if ((unsigned)index >= (unsigned)mat->dims) {
            CV_Error(CV_StsOutOfRange, "bad dimension index");
        }

        size = mat->dim[index].size;
    } else if (CV_IS_SPARSE_MAT_HDR(arr)) {
        CvSparseMat* mat = (CvSparseMat*)arr;

        if ((unsigned)index >= (unsigned)mat->dims) {
            CV_Error(CV_StsOutOfRange, "bad dimension index");
        }

        size = mat->size[index];
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return size;
}


// Returns the size of CvMat or IplImage
CV_IMPL CvSize
cvGetSize(const CvArr* arr) {
    CvSize size = { 0, 0 };

    if (CV_IS_MAT_HDR(arr)) {
        CvMat* mat = (CvMat*)arr;

        size.width = mat->cols;
        size.height = mat->rows;
    } else if (CV_IS_IMAGE_HDR(arr)) {
        IplImage* img = (IplImage*)arr;

        if (img->roi) {
            size.width = img->roi->width;
            size.height = img->roi->height;
        } else {
            size.width = img->width;
            size.height = img->height;
        }
    } else {
        CV_Error(CV_StsBadArg, "Array should be CvMat or IplImage");
    }

    return size;
}


// Selects sub-array (no data is copied)
CV_IMPL  CvMat*
cvGetSubRect(const CvArr* arr, CvMat* submat, CvRect rect) {
    CvMat* res = 0;
    CvMat stub, *mat = (CvMat*)arr;

    if (!CV_IS_MAT(mat)) {
        mat = cvGetMat(mat, &stub);
    }

    if (!submat) {
        CV_Error(CV_StsNullPtr, "");
    }

    if ((rect.x | rect.y | rect.width | rect.height) < 0) {
        CV_Error(CV_StsBadSize, "");
    }

    if (rect.x + rect.width > mat->cols ||
            rect.y + rect.height > mat->rows) {
        CV_Error(CV_StsBadSize, "");
    }

    {
        /*
        int* refcount = mat->refcount;

        if( refcount )
            ++*refcount;

        cvDecRefData( submat );
        */
        submat->data.ptr = mat->data.ptr + (size_t)rect.y * mat->step +
                           rect.x * CV_ELEM_SIZE(mat->type);
        submat->step = mat->step;
        submat->type = (mat->type & (rect.width < mat->cols ? ~CV_MAT_CONT_FLAG : -1)) |
                       (rect.height <= 1 ? CV_MAT_CONT_FLAG : 0);
        submat->rows = rect.height;
        submat->cols = rect.width;
        submat->refcount = 0;
        res = submat;
    }

    return res;
}


// Selects array's row span.
CV_IMPL  CvMat*
cvGetRows(const CvArr* arr, CvMat* submat,
          int start_row, int end_row, int delta_row) {
    CvMat* res = 0;
    CvMat stub, *mat = (CvMat*)arr;

    if (!CV_IS_MAT(mat)) {
        mat = cvGetMat(mat, &stub);
    }

    if (!submat) {
        CV_Error(CV_StsNullPtr, "");
    }

    if ((unsigned)start_row >= (unsigned)mat->rows ||
            (unsigned)end_row > (unsigned)mat->rows || delta_row <= 0) {
        CV_Error(CV_StsOutOfRange, "");
    }

    {
        /*
        int* refcount = mat->refcount;

        if( refcount )
            ++*refcount;

        cvDecRefData( submat );
        */
        if (delta_row == 1) {
            submat->rows = end_row - start_row;
            submat->step = mat->step;
        } else {
            submat->rows = (end_row - start_row + delta_row - 1) / delta_row;
            submat->step = mat->step * delta_row;
        }

        submat->cols = mat->cols;
        submat->step &= submat->rows > 1 ? -1 : 0;
        submat->data.ptr = mat->data.ptr + (size_t)start_row * mat->step;
        submat->type = (mat->type | (submat->rows == 1 ? CV_MAT_CONT_FLAG : 0)) &
                       (delta_row != 1 && submat->rows > 1 ? ~CV_MAT_CONT_FLAG : -1);
        submat->refcount = 0;
        submat->hdr_refcount = 0;
        res = submat;
    }

    return res;
}


// Selects array's column span.
CV_IMPL  CvMat*
cvGetCols(const CvArr* arr, CvMat* submat, int start_col, int end_col) {
    CvMat* res = 0;
    CvMat stub, *mat = (CvMat*)arr;
    int cols;

    if (!CV_IS_MAT(mat)) {
        mat = cvGetMat(mat, &stub);
    }

    if (!submat) {
        CV_Error(CV_StsNullPtr, "");
    }

    cols = mat->cols;
    if ((unsigned)start_col >= (unsigned)cols ||
            (unsigned)end_col > (unsigned)cols) {
        CV_Error(CV_StsOutOfRange, "");
    }

    {
        /*
        int* refcount = mat->refcount;

        if( refcount )
            ++*refcount;

        cvDecRefData( submat );
        */
        submat->rows = mat->rows;
        submat->cols = end_col - start_col;
        submat->step = mat->step;
        submat->data.ptr = mat->data.ptr + (size_t)start_col * CV_ELEM_SIZE(mat->type);
        submat->type = mat->type & (submat->rows > 1 && submat->cols < cols ? ~CV_MAT_CONT_FLAG : -1);
        submat->refcount = 0;
        submat->hdr_refcount = 0;
        res = submat;
    }

    return res;
}


// Selects array diagonal
CV_IMPL  CvMat*
cvGetDiag(const CvArr* arr, CvMat* submat, int diag) {
    CvMat* res = 0;
    CvMat stub, *mat = (CvMat*)arr;
    int len, pix_size;

    if (!CV_IS_MAT(mat)) {
        mat = cvGetMat(mat, &stub);
    }

    if (!submat) {
        CV_Error(CV_StsNullPtr, "");
    }

    pix_size = CV_ELEM_SIZE(mat->type);

    /*{
    int* refcount = mat->refcount;

    if( refcount )
        ++*refcount;

    cvDecRefData( submat );
    }*/

    if (diag >= 0) {
        len = mat->cols - diag;

        if (len <= 0) {
            CV_Error(CV_StsOutOfRange, "");
        }

        len = CV_IMIN(len, mat->rows);
        submat->data.ptr = mat->data.ptr + diag * pix_size;
    } else {
        len = mat->rows + diag;

        if (len <= 0) {
            CV_Error(CV_StsOutOfRange, "");
        }

        len = CV_IMIN(len, mat->cols);
        submat->data.ptr = mat->data.ptr - diag * mat->step;
    }

    submat->rows = len;
    submat->cols = 1;
    submat->step = mat->step + (submat->rows > 1 ? pix_size : 0);
    submat->type = mat->type;
    if (submat->rows > 1) {
        submat->type &= ~CV_MAT_CONT_FLAG;
    } else {
        submat->type |= CV_MAT_CONT_FLAG;
    }
    submat->refcount = 0;
    submat->hdr_refcount = 0;
    res = submat;

    return res;
}


/****************************************************************************************\
*                      Operations on CvScalar and accessing array elements               *
\****************************************************************************************/

// Converts CvScalar to specified type
CV_IMPL void
cvScalarToRawData(const CvScalar* scalar, void* data, int type, int extend_to_12) {
    type = CV_MAT_TYPE(type);
    int cn = CV_MAT_CN(type);
    int depth = type & CV_MAT_DEPTH_MASK;

    assert(scalar && data);
    if ((unsigned)(cn - 1) >= 4) {
        CV_Error(CV_StsOutOfRange, "The number of channels must be 1, 2, 3 or 4");
    }

    switch (depth) {
    case CV_8UC1:
        while (cn--) {
            int t = cvRound(scalar->val[cn]);
            ((uchar*)data)[cn] = CV_CAST_8U(t);
        }
        break;
    case CV_8SC1:
        while (cn--) {
            int t = cvRound(scalar->val[cn]);
            ((char*)data)[cn] = CV_CAST_8S(t);
        }
        break;
    case CV_16UC1:
        while (cn--) {
            int t = cvRound(scalar->val[cn]);
            ((ushort*)data)[cn] = CV_CAST_16U(t);
        }
        break;
    case CV_16SC1:
        while (cn--) {
            int t = cvRound(scalar->val[cn]);
            ((short*)data)[cn] = CV_CAST_16S(t);
        }
        break;
    case CV_32SC1:
        while (cn--) {
            ((int*)data)[cn] = cvRound(scalar->val[cn]);
        }
        break;
    case CV_32FC1:
        while (cn--) {
            ((float*)data)[cn] = (float)(scalar->val[cn]);
        }
        break;
    case CV_64FC1:
        while (cn--) {
            ((double*)data)[cn] = (double)(scalar->val[cn]);
        }
        break;
    default:
        assert(0);
        CV_Error(CV_BadDepth, "");
    }

    if (extend_to_12) {
        int pix_size = CV_ELEM_SIZE(type);
        int offset = CV_ELEM_SIZE1(depth) * 12;

        do {
            offset -= pix_size;
            CV_MEMCPY_AUTO((char*)data + offset, data, pix_size);
        } while (offset > pix_size);
    }
}


// Converts data of specified type to CvScalar
CV_IMPL void
cvRawDataToScalar(const void* data, int flags, CvScalar* scalar) {
    int cn = CV_MAT_CN(flags);

    assert(scalar && data);

    if ((unsigned)(cn - 1) >= 4) {
        CV_Error(CV_StsOutOfRange, "The number of channels must be 1, 2, 3 or 4");
    }

    memset(scalar->val, 0, sizeof(scalar->val));

    switch (CV_MAT_DEPTH(flags)) {
    case CV_8U:
        while (cn--) {
            scalar->val[cn] = CV_8TO32F(((uchar*)data)[cn]);
        }
        break;
    case CV_8S:
        while (cn--) {
            scalar->val[cn] = CV_8TO32F(((char*)data)[cn]);
        }
        break;
    case CV_16U:
        while (cn--) {
            scalar->val[cn] = ((ushort*)data)[cn];
        }
        break;
    case CV_16S:
        while (cn--) {
            scalar->val[cn] = ((short*)data)[cn];
        }
        break;
    case CV_32S:
        while (cn--) {
            scalar->val[cn] = ((int*)data)[cn];
        }
        break;
    case CV_32F:
        while (cn--) {
            scalar->val[cn] = ((float*)data)[cn];
        }
        break;
    case CV_64F:
        while (cn--) {
            scalar->val[cn] = ((double*)data)[cn];
        }
        break;
    default:
        assert(0);
        CV_Error(CV_BadDepth, "");
    }
}


static double icvGetReal(const void* data, int type) {
    switch (type) {
    case CV_8U:
        return *(uchar*)data;
    case CV_8S:
        return *(char*)data;
    case CV_16U:
        return *(ushort*)data;
    case CV_16S:
        return *(short*)data;
    case CV_32S:
        return *(int*)data;
    case CV_32F:
        return *(float*)data;
    case CV_64F:
        return *(double*)data;
    }

    return 0;
}


static void icvSetReal(double value, const void* data, int type) {
    if (type < CV_32F) {
        int ivalue = cvRound(value);
        switch (type) {
        case CV_8U:
            *(uchar*)data = CV_CAST_8U(ivalue);
            break;
        case CV_8S:
            *(char*)data = CV_CAST_8S(ivalue);
            break;
        case CV_16U:
            *(ushort*)data = CV_CAST_16U(ivalue);
            break;
        case CV_16S:
            *(short*)data = CV_CAST_16S(ivalue);
            break;
        case CV_32S:
            *(int*)data = CV_CAST_32S(ivalue);
            break;
        }
    } else {
        switch (type) {
        case CV_32F:
            *(float*)data = (float)value;
            break;
        case CV_64F:
            *(double*)data = value;
            break;
        }
    }
}


// Returns pointer to specified element of array (linear index is used)
CV_IMPL  uchar*
cvPtr1D(const CvArr* arr, int idx, int* _type) {
    uchar* ptr = 0;
    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        int type = CV_MAT_TYPE(mat->type);
        int pix_size = CV_ELEM_SIZE(type);

        if (_type) {
            *_type = type;
        }

        // the first part is mul-free sufficient check
        // that the index is within the matrix
        if ((unsigned)idx >= (unsigned)(mat->rows + mat->cols - 1) &&
                (unsigned)idx >= (unsigned)(mat->rows * mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        if (CV_IS_MAT_CONT(mat->type)) {
            ptr = mat->data.ptr + (size_t)idx * pix_size;
        } else {
            int row, col;
            if (mat->cols == 1) {
                row = idx, col = 0;
            } else {
                row = idx / mat->cols, col = idx - row * mat->cols;
            }
            ptr = mat->data.ptr + (size_t)row * mat->step + col * pix_size;
        }
    } else if (CV_IS_IMAGE_HDR(arr)) {
        IplImage* img = (IplImage*)arr;
        int width = !img->roi ? img->width : img->roi->width;
        int y = idx / width, x = idx - y * width;

        ptr = cvPtr2D(arr, y, x, _type);
    } else if (CV_IS_MATND(arr)) {
        CvMatND* mat = (CvMatND*)arr;
        int j, type = CV_MAT_TYPE(mat->type);
        size_t size = mat->dim[0].size;

        if (_type) {
            *_type = type;
        }

        for (j = 1; j < mat->dims; j++) {
            size *= mat->dim[j].size;
        }

        if ((unsigned)idx >= (unsigned)size) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        if (CV_IS_MAT_CONT(mat->type)) {
            int pix_size = CV_ELEM_SIZE(type);
            ptr = mat->data.ptr + (size_t)idx * pix_size;
        } else {
            ptr = mat->data.ptr;
            for (j = mat->dims - 1; j >= 0; j--) {
                int sz = mat->dim[j].size;
                if (sz) {
                    int t = idx / sz;
                    ptr += (idx - t * sz) * mat->dim[j].step;
                    idx = t;
                }
            }
        }
    } else if (CV_IS_SPARSE_MAT(arr)) {
        CvSparseMat* m = (CvSparseMat*)arr;
        if (m->dims == 1) {
            ptr = icvGetNodePtr((CvSparseMat*)arr, &idx, _type, 1, 0);
        } else {
            int i, n = m->dims;
            int* _idx = (int*)cvStackAlloc(n * sizeof(_idx[0]));

            for (i = n - 1; i >= 0; i--) {
                int t = idx / m->size[i];
                _idx[i] = idx - t * m->size[i];
                idx = t;
            }
            ptr = icvGetNodePtr((CvSparseMat*)arr, _idx, _type, 1, 0);
        }
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return ptr;
}


// Returns pointer to specified element of 2d array
CV_IMPL  uchar*
cvPtr2D(const CvArr* arr, int y, int x, int* _type) {
    uchar* ptr = 0;
    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;
        int type;

        if ((unsigned)y >= (unsigned)(mat->rows) ||
                (unsigned)x >= (unsigned)(mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        type = CV_MAT_TYPE(mat->type);
        if (_type) {
            *_type = type;
        }

        ptr = mat->data.ptr + (size_t)y * mat->step + x * CV_ELEM_SIZE(type);
    } else if (CV_IS_IMAGE(arr)) {
        IplImage* img = (IplImage*)arr;
        int pix_size = (img->depth & 255) >> 3;
        int width, height;
        ptr = (uchar*)img->imageData;

        if (img->dataOrder == 0) {
            pix_size *= img->nChannels;
        }

        if (img->roi) {
            width = img->roi->width;
            height = img->roi->height;

            ptr += img->roi->yOffset * img->widthStep +
                   img->roi->xOffset * pix_size;

            if (img->dataOrder) {
                int coi = img->roi->coi;
                if (!coi)
                    CV_Error(CV_BadCOI,
                             "COI must be non-null in case of planar images");
                ptr += (coi - 1) * img->imageSize;
            }
        } else {
            width = img->width;
            height = img->height;
        }

        if ((unsigned)y >= (unsigned)height ||
                (unsigned)x >= (unsigned)width) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr += y * img->widthStep + x * pix_size;

        if (_type) {
            int type = IPL2CV_DEPTH(img->depth);
            if (type < 0 || (unsigned)(img->nChannels - 1) > 3) {
                CV_Error(CV_StsUnsupportedFormat, "");
            }

            *_type = CV_MAKETYPE(type, img->nChannels);
        }
    } else if (CV_IS_MATND(arr)) {
        CvMatND* mat = (CvMatND*)arr;

        if (mat->dims != 2 ||
                (unsigned)y >= (unsigned)(mat->dim[0].size) ||
                (unsigned)x >= (unsigned)(mat->dim[1].size)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)y * mat->dim[0].step + x * mat->dim[1].step;
        if (_type) {
            *_type = CV_MAT_TYPE(mat->type);
        }
    } else if (CV_IS_SPARSE_MAT(arr)) {
        int idx[] = { y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, _type, 1, 0);
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return ptr;
}


// Returns pointer to specified element of 3d array
CV_IMPL  uchar*
cvPtr3D(const CvArr* arr, int z, int y, int x, int* _type) {
    uchar* ptr = 0;
    if (CV_IS_MATND(arr)) {
        CvMatND* mat = (CvMatND*)arr;

        if (mat->dims != 3 ||
                (unsigned)z >= (unsigned)(mat->dim[0].size) ||
                (unsigned)y >= (unsigned)(mat->dim[1].size) ||
                (unsigned)x >= (unsigned)(mat->dim[2].size)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)z * mat->dim[0].step +
              (size_t)y * mat->dim[1].step + x * mat->dim[2].step;

        if (_type) {
            *_type = CV_MAT_TYPE(mat->type);
        }
    } else if (CV_IS_SPARSE_MAT(arr)) {
        int idx[] = { z, y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, _type, 1, 0);
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return ptr;
}


// Returns pointer to specified element of n-d array
CV_IMPL  uchar*
cvPtrND(const CvArr* arr, const int* idx, int* _type,
        int create_node, unsigned* precalc_hashval) {
    uchar* ptr = 0;
    if (!idx) {
        CV_Error(CV_StsNullPtr, "NULL pointer to indices");
    }

    if (CV_IS_SPARSE_MAT(arr))
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx,
                            _type, create_node, precalc_hashval);
    else if (CV_IS_MATND(arr)) {
        CvMatND* mat = (CvMatND*)arr;
        int i;
        ptr = mat->data.ptr;

        for (i = 0; i < mat->dims; i++) {
            if ((unsigned)idx[i] >= (unsigned)(mat->dim[i].size)) {
                CV_Error(CV_StsOutOfRange, "index is out of range");
            }
            ptr += (size_t)idx[i] * mat->dim[i].step;
        }

        if (_type) {
            *_type = CV_MAT_TYPE(mat->type);
        }
    } else if (CV_IS_MAT_HDR(arr) || CV_IS_IMAGE_HDR(arr)) {
        ptr = cvPtr2D(arr, idx[0], idx[1], _type);
    } else {
        CV_Error(CV_StsBadArg, "unrecognized or unsupported array type");
    }

    return ptr;
}


// Returns specifed element of n-D array given linear index
CV_IMPL  CvScalar
cvGet1D(const CvArr* arr, int idx) {
    CvScalar scalar = {{0, 0, 0, 0}};
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr) && CV_IS_MAT_CONT(((CvMat*)arr)->type)) {
        CvMat* mat = (CvMat*)arr;

        type = CV_MAT_TYPE(mat->type);
        int pix_size = CV_ELEM_SIZE(type);

        // the first part is mul-free sufficient check
        // that the index is within the matrix
        if ((unsigned)idx >= (unsigned)(mat->rows + mat->cols - 1) &&
                (unsigned)idx >= (unsigned)(mat->rows * mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)idx * pix_size;
    } else if (!CV_IS_SPARSE_MAT(arr) || ((CvSparseMat*)arr)->dims > 1) {
        ptr = cvPtr1D(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, &idx, &type, 0, 0);
    }

    if (ptr) {
        cvRawDataToScalar(ptr, type, &scalar);
    }

    return scalar;
}


// Returns specifed element of 2D array
CV_IMPL  CvScalar
cvGet2D(const CvArr* arr, int y, int x) {
    CvScalar scalar = {{0, 0, 0, 0}};
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        if ((unsigned)y >= (unsigned)(mat->rows) ||
                (unsigned)x >= (unsigned)(mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        type = CV_MAT_TYPE(mat->type);
        ptr = mat->data.ptr + (size_t)y * mat->step + x * CV_ELEM_SIZE(type);
    } else if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr2D(arr, y, x, &type);
    } else {
        int idx[] = { y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        cvRawDataToScalar(ptr, type, &scalar);
    }

    return scalar;
}


// Returns specifed element of 3D array
CV_IMPL  CvScalar
cvGet3D(const CvArr* arr, int z, int y, int x) {
    CvScalar scalar = {{0, 0, 0, 0}};
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr3D(arr, z, y, x, &type);
    } else {
        int idx[] = { z, y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        cvRawDataToScalar(ptr, type, &scalar);
    }
    return scalar;
}


// Returns specifed element of nD array
CV_IMPL  CvScalar
cvGetND(const CvArr* arr, const int* idx) {
    CvScalar scalar = {{0, 0, 0, 0}};
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtrND(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        cvRawDataToScalar(ptr, type, &scalar);
    }

    return scalar;
}


// Returns specifed element of n-D array given linear index
CV_IMPL  double
cvGetReal1D(const CvArr* arr, int idx) {
    double value = 0;
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr) && CV_IS_MAT_CONT(((CvMat*)arr)->type)) {
        CvMat* mat = (CvMat*)arr;

        type = CV_MAT_TYPE(mat->type);
        int pix_size = CV_ELEM_SIZE(type);

        // the first part is mul-free sufficient check
        // that the index is within the matrix
        if ((unsigned)idx >= (unsigned)(mat->rows + mat->cols - 1) &&
                (unsigned)idx >= (unsigned)(mat->rows * mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)idx * pix_size;
    } else if (!CV_IS_SPARSE_MAT(arr) || ((CvSparseMat*)arr)->dims > 1) {
        ptr = cvPtr1D(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, &idx, &type, 0, 0);
    }

    if (ptr) {
        if (CV_MAT_CN(type) > 1) {
            CV_Error(CV_BadNumChannels, "cvGetReal* support only single-channel arrays");
        }

        value = icvGetReal(ptr, type);
    }
    return value;
}


// Returns specifed element of 2D array
CV_IMPL  double
cvGetReal2D(const CvArr* arr, int y, int x) {
    double value = 0;
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        if ((unsigned)y >= (unsigned)(mat->rows) ||
                (unsigned)x >= (unsigned)(mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        type = CV_MAT_TYPE(mat->type);
        ptr = mat->data.ptr + (size_t)y * mat->step + x * CV_ELEM_SIZE(type);
    } else if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr2D(arr, y, x, &type);
    } else {
        int idx[] = { y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        if (CV_MAT_CN(type) > 1) {
            CV_Error(CV_BadNumChannels, "cvGetReal* support only single-channel arrays");
        }

        value = icvGetReal(ptr, type);
    }

    return value;
}


// Returns specifed element of 3D array
CV_IMPL  double
cvGetReal3D(const CvArr* arr, int z, int y, int x) {
    double value = 0;
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr3D(arr, z, y, x, &type);
    } else {
        int idx[] = { z, y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        if (CV_MAT_CN(type) > 1) {
            CV_Error(CV_BadNumChannels, "cvGetReal* support only single-channel arrays");
        }

        value = icvGetReal(ptr, type);
    }

    return value;
}


// Returns specifed element of nD array
CV_IMPL  double
cvGetRealND(const CvArr* arr, const int* idx) {
    double value = 0;
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtrND(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, 0, 0);
    }

    if (ptr) {
        if (CV_MAT_CN(type) > 1) {
            CV_Error(CV_BadNumChannels, "cvGetReal* support only single-channel arrays");
        }

        value = icvGetReal(ptr, type);
    }

    return value;
}


// Assigns new value to specifed element of nD array given linear index
CV_IMPL  void
cvSet1D(CvArr* arr, int idx, CvScalar scalar) {
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr) && CV_IS_MAT_CONT(((CvMat*)arr)->type)) {
        CvMat* mat = (CvMat*)arr;

        type = CV_MAT_TYPE(mat->type);
        int pix_size = CV_ELEM_SIZE(type);

        // the first part is mul-free sufficient check
        // that the index is within the matrix
        if ((unsigned)idx >= (unsigned)(mat->rows + mat->cols - 1) &&
                (unsigned)idx >= (unsigned)(mat->rows * mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)idx * pix_size;
    } else if (!CV_IS_SPARSE_MAT(arr) || ((CvSparseMat*)arr)->dims > 1) {
        ptr = cvPtr1D(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, &idx, &type, -1, 0);
    }

    cvScalarToRawData(&scalar, ptr, type);
}


// Assigns new value to specifed element of 2D array
CV_IMPL  void
cvSet2D(CvArr* arr, int y, int x, CvScalar scalar) {
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        if ((unsigned)y >= (unsigned)(mat->rows) ||
                (unsigned)x >= (unsigned)(mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        type = CV_MAT_TYPE(mat->type);
        ptr = mat->data.ptr + (size_t)y * mat->step + x * CV_ELEM_SIZE(type);
    } else if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr2D(arr, y, x, &type);
    } else {
        int idx[] = { y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }
    cvScalarToRawData(&scalar, ptr, type);
}


// Assigns new value to specifed element of 3D array
CV_IMPL  void
cvSet3D(CvArr* arr, int z, int y, int x, CvScalar scalar) {
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr3D(arr, z, y, x, &type);
    } else {
        int idx[] = { z, y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }
    cvScalarToRawData(&scalar, ptr, type);
}


// Assigns new value to specifed element of nD array
CV_IMPL  void
cvSetND(CvArr* arr, const int* idx, CvScalar scalar) {
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtrND(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }
    cvScalarToRawData(&scalar, ptr, type);
}


CV_IMPL  void
cvSetReal1D(CvArr* arr, int idx, double value) {
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr) && CV_IS_MAT_CONT(((CvMat*)arr)->type)) {
        CvMat* mat = (CvMat*)arr;

        type = CV_MAT_TYPE(mat->type);
        int pix_size = CV_ELEM_SIZE(type);

        // the first part is mul-free sufficient check
        // that the index is within the matrix
        if ((unsigned)idx >= (unsigned)(mat->rows + mat->cols - 1) &&
                (unsigned)idx >= (unsigned)(mat->rows * mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        ptr = mat->data.ptr + (size_t)idx * pix_size;
    } else if (!CV_IS_SPARSE_MAT(arr) || ((CvSparseMat*)arr)->dims > 1) {
        ptr = cvPtr1D(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, &idx, &type, -1, 0);
    }

    if (CV_MAT_CN(type) > 1) {
        CV_Error(CV_BadNumChannels, "cvSetReal* support only single-channel arrays");
    }

    if (ptr) {
        icvSetReal(value, ptr, type);
    }
}


CV_IMPL  void
cvSetReal2D(CvArr* arr, int y, int x, double value) {
    int type = 0;
    uchar* ptr;

    if (CV_IS_MAT(arr)) {
        CvMat* mat = (CvMat*)arr;

        if ((unsigned)y >= (unsigned)(mat->rows) ||
                (unsigned)x >= (unsigned)(mat->cols)) {
            CV_Error(CV_StsOutOfRange, "index is out of range");
        }

        type = CV_MAT_TYPE(mat->type);
        ptr = mat->data.ptr + (size_t)y * mat->step + x * CV_ELEM_SIZE(type);
    } else if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr2D(arr, y, x, &type);
    } else {
        int idx[] = { y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }
    if (CV_MAT_CN(type) > 1) {
        CV_Error(CV_BadNumChannels, "cvSetReal* support only single-channel arrays");
    }

    if (ptr) {
        icvSetReal(value, ptr, type);
    }
}


CV_IMPL  void
cvSetReal3D(CvArr* arr, int z, int y, int x, double value) {
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtr3D(arr, z, y, x, &type);
    } else {
        int idx[] = { z, y, x };
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }
    if (CV_MAT_CN(type) > 1) {
        CV_Error(CV_BadNumChannels, "cvSetReal* support only single-channel arrays");
    }

    if (ptr) {
        icvSetReal(value, ptr, type);
    }
}


CV_IMPL  void
cvSetRealND(CvArr* arr, const int* idx, double value) {
    int type = 0;
    uchar* ptr;

    if (!CV_IS_SPARSE_MAT(arr)) {
        ptr = cvPtrND(arr, idx, &type);
    } else {
        ptr = icvGetNodePtr((CvSparseMat*)arr, idx, &type, -1, 0);
    }

    if (CV_MAT_CN(type) > 1) {
        CV_Error(CV_BadNumChannels, "cvSetReal* support only single-channel arrays");
    }

    if (ptr) {
        icvSetReal(value, ptr, type);
    }
}


CV_IMPL void
cvClearND(CvArr* arr, const int* idx) {
    if (!CV_IS_SPARSE_MAT(arr)) {
        int type;
        uchar* ptr;
        ptr = cvPtrND(arr, idx, &type);
        if (ptr) {
            CV_ZERO_CHAR(ptr, CV_ELEM_SIZE(type));
        }
    } else {
        icvDeleteNode((CvSparseMat*)arr, idx, 0);
    }
}


/****************************************************************************************\
*                             Conversion to CvMat or IplImage                            *
\****************************************************************************************/

// convert array (CvMat or IplImage) to CvMat
CV_IMPL CvMat*
cvGetMat(const CvArr* array, CvMat* mat,
         int* pCOI, int allowND) {
    CvMat* result = 0;
    CvMat* src = (CvMat*)array;
    int coi = 0;

    if (!mat || !src) {
        CV_Error(CV_StsNullPtr, "NULL array pointer is passed");
    }

    if (CV_IS_MAT_HDR(src)) {
        if (!src->data.ptr) {
            CV_Error(CV_StsNullPtr, "The matrix has NULL data pointer");
        }

        result = (CvMat*)src;
    } else if (CV_IS_IMAGE_HDR(src)) {
        const IplImage* img = (const IplImage*)src;
        int depth, order;

        if (img->imageData == 0) {
            CV_Error(CV_StsNullPtr, "The image has NULL data pointer");
        }

        depth = IPL2CV_DEPTH(img->depth);
        if (depth < 0) {
            CV_Error(CV_BadDepth, "");
        }

        order = img->dataOrder & (img->nChannels > 1 ? -1 : 0);

        if (img->roi) {
            if (order == IPL_DATA_ORDER_PLANE) {
                int type = depth;

                if (img->roi->coi == 0)
                    CV_Error(CV_StsBadFlag,
                             "Images with planar data layout should be used with COI selected");

                cvInitMatHeader(mat, img->roi->height,
                                img->roi->width, type,
                                img->imageData + (img->roi->coi - 1)*img->imageSize +
                                img->roi->yOffset * img->widthStep +
                                img->roi->xOffset * CV_ELEM_SIZE(type),
                                img->widthStep);
            } else { /* pixel order */
                int type = CV_MAKETYPE(depth, img->nChannels);
                coi = img->roi->coi;

                if (img->nChannels > CV_CN_MAX)
                    CV_Error(CV_BadNumChannels,
                             "The image is interleaved and has over CV_CN_MAX channels");

                cvInitMatHeader(mat, img->roi->height, img->roi->width,
                                type, img->imageData +
                                img->roi->yOffset * img->widthStep +
                                img->roi->xOffset * CV_ELEM_SIZE(type),
                                img->widthStep);
            }
        } else {
            int type = CV_MAKETYPE(depth, img->nChannels);

            if (order != IPL_DATA_ORDER_PIXEL) {
                CV_Error(CV_StsBadFlag, "Pixel order should be used with coi == 0");
            }

            cvInitMatHeader(mat, img->height, img->width, type,
                            img->imageData, img->widthStep);
        }

        result = mat;
    } else if (allowND && CV_IS_MATND_HDR(src)) {
        CvMatND* matnd = (CvMatND*)src;
        int i;
        int size1 = matnd->dim[0].size, size2 = 1;

        if (!src->data.ptr) {
            CV_Error(CV_StsNullPtr, "Input array has NULL data pointer");
        }

        if (!CV_IS_MAT_CONT(matnd->type)) {
            CV_Error(CV_StsBadArg, "Only continuous nD arrays are supported here");
        }

        if (matnd->dims > 2)
            for (i = 1; i < matnd->dims; i++) {
                size2 *= matnd->dim[i].size;
            }
        else {
            size2 = matnd->dims == 1 ? 1 : matnd->dim[1].size;
        }

        mat->refcount = 0;
        mat->hdr_refcount = 0;
        mat->data.ptr = matnd->data.ptr;
        mat->rows = size1;
        mat->cols = size2;
        mat->type = CV_MAT_TYPE(matnd->type) | CV_MAT_MAGIC_VAL | CV_MAT_CONT_FLAG;
        mat->step = size2 * CV_ELEM_SIZE(matnd->type);
        mat->step &= size1 > 1 ? -1 : 0;

        icvCheckHuge(mat);
        result = mat;
    } else {
        CV_Error(CV_StsBadFlag, "Unrecognized or unsupported array type");
    }

    if (pCOI) {
        *pCOI = coi;
    }

    return result;
}


CV_IMPL CvArr*
cvReshapeMatND(const CvArr* arr,
               int sizeof_header, CvArr* _header,
               int new_cn, int new_dims, int* new_sizes) {
    CvArr* result = 0;
    int dims, coi = 0;

    if (!arr || !_header) {
        CV_Error(CV_StsNullPtr, "NULL pointer to array or destination header");
    }

    if (new_cn == 0 && new_dims == 0) {
        CV_Error(CV_StsBadArg, "None of array parameters is changed: dummy call?");
    }

    dims = cvGetDims(arr);

    if (new_dims == 0) {
        new_sizes = 0;
        new_dims = dims;
    } else if (new_dims == 1) {
        new_sizes = 0;
    } else {
        if (new_dims <= 0 || new_dims > CV_MAX_DIM) {
            CV_Error(CV_StsOutOfRange, "Non-positive or too large number of dimensions");
        }
        if (!new_sizes) {
            CV_Error(CV_StsNullPtr, "New dimension sizes are not specified");
        }
    }

    if (new_dims <= 2) {
        CvMat* mat = (CvMat*)arr;
        CvMat header;
        int* refcount = 0;
        int  hdr_refcount = 0;
        int  total_width, new_rows, cn;

        if (sizeof_header != sizeof(CvMat) && sizeof_header != sizeof(CvMatND)) {
            CV_Error(CV_StsBadArg, "The output header should be CvMat or CvMatND");
        }

        if (mat == (CvMat*)_header) {
            refcount = mat->refcount;
            hdr_refcount = mat->hdr_refcount;
        }

        if (!CV_IS_MAT(mat)) {
            mat = cvGetMat(mat, &header, &coi, 1);
        }

        cn = CV_MAT_CN(mat->type);
        total_width = mat->cols * cn;

        if (new_cn == 0) {
            new_cn = cn;
        }

        if (new_sizes) {
            new_rows = new_sizes[0];
        } else if (new_dims == 1) {
            new_rows = total_width * mat->rows / new_cn;
        } else {
            new_rows = mat->rows;
            if (new_cn > total_width) {
                new_rows = mat->rows * total_width / new_cn;
            }
        }

        if (new_rows != mat->rows) {
            int total_size = total_width * mat->rows;

            if (!CV_IS_MAT_CONT(mat->type))
                CV_Error(CV_BadStep,
                         "The matrix is not continuous so the number of rows can not be changed");

            total_width = total_size / new_rows;

            if (total_width* new_rows != total_size)
                CV_Error(CV_StsBadArg, "The total number of matrix elements "
                         "is not divisible by the new number of rows");
        }

        header.rows = new_rows;
        header.cols = total_width / new_cn;

        if (header.cols* new_cn != total_width ||
                (new_sizes && header.cols != new_sizes[1]))
            CV_Error(CV_StsBadArg, "The total matrix width is not "
                     "divisible by the new number of columns");

        header.type = (mat->type & ~CV_MAT_TYPE_MASK) | CV_MAKETYPE(mat->type, new_cn);
        header.step = header.cols * CV_ELEM_SIZE(mat->type);
        header.step &= new_rows > 1 ? -1 : 0;
        header.refcount = refcount;
        header.hdr_refcount = hdr_refcount;

        if (sizeof_header == sizeof(CvMat)) {
            *(CvMat*)_header = header;
        } else {
            CvMatND* __header = (CvMatND*)_header;
            cvGetMatND(&header, __header, 0);
            if (new_dims > 0) {
                __header->dims = new_dims;
            }
        }
    } else {
        CvMatND* header = (CvMatND*)_header;

        if (sizeof_header != sizeof(CvMatND)) {
            CV_Error(CV_StsBadSize, "The output header should be CvMatND");
        }

        if (!new_sizes) {
            if (!CV_IS_MATND(arr)) {
                CV_Error(CV_StsBadArg, "The input array must be CvMatND");
            }

            {
                CvMatND* mat = (CvMatND*)arr;
                assert(new_cn > 0);
                int last_dim_size = mat->dim[mat->dims - 1].size * CV_MAT_CN(mat->type);
                int new_size = last_dim_size / new_cn;

                if (new_size* new_cn != last_dim_size)
                    CV_Error(CV_StsBadArg,
                             "The last dimension full size is not divisible by new number of channels");

                if (mat != header) {
                    memcpy(header, mat, sizeof(*header));
                    header->refcount = 0;
                    header->hdr_refcount = 0;
                }

                header->dim[header->dims - 1].size = new_size;
                header->type = (header->type & ~CV_MAT_TYPE_MASK) | CV_MAKETYPE(header->type, new_cn);
            }
        } else {
            CvMatND stub;
            CvMatND* mat = (CvMatND*)arr;
            int i, size1, size2;
            int step;

            if (new_cn != 0)
                CV_Error(CV_StsBadArg,
                         "Simultaneous change of shape and number of channels is not supported. "
                         "Do it by 2 separate calls");

            if (!CV_IS_MATND(mat)) {
                cvGetMatND(mat, &stub, &coi);
                mat = &stub;
            }

            if (CV_IS_MAT_CONT(mat->type)) {
                CV_Error(CV_StsBadArg, "Non-continuous nD arrays are not supported");
            }

            size1 = mat->dim[0].size;
            for (i = 1; i < dims; i++) {
                size1 *= mat->dim[i].size;
            }

            size2 = 1;
            for (i = 0; i < new_dims; i++) {
                if (new_sizes[i] <= 0)
                    CV_Error(CV_StsBadSize,
                             "One of new dimension sizes is non-positive");
                size2 *= new_sizes[i];
            }

            if (size1 != size2)
                CV_Error(CV_StsBadSize,
                         "Number of elements in the original and reshaped array is different");

            if (header != mat) {
                header->refcount = 0;
                header->hdr_refcount = 0;
            }

            header->dims = new_dims;
            header->type = mat->type;
            header->data.ptr = mat->data.ptr;
            step = CV_ELEM_SIZE(header->type);

            for (i = new_dims - 1; i >= 0; i--) {
                header->dim[i].size = new_sizes[i];
                header->dim[i].step = step;
                step *= new_sizes[i];
            }
        }
    }

    if (coi) {
        CV_Error(CV_BadCOI, "COI is not supported by this operation");
    }

    result = _header;
    return result;
}


CV_IMPL CvMat*
cvReshape(const CvArr* array, CvMat* header,
          int new_cn, int new_rows) {
    CvMat* result = 0;
    CvMat* mat = (CvMat*)array;
    int total_width, new_width;

    if (!header) {
        CV_Error(CV_StsNullPtr, "");
    }

    if (!CV_IS_MAT(mat)) {
        int coi = 0;
        mat = cvGetMat(mat, header, &coi, 1);
        if (coi) {
            CV_Error(CV_BadCOI, "COI is not supported");
        }
    }

    if (new_cn == 0) {
        new_cn = CV_MAT_CN(mat->type);
    } else if ((unsigned)(new_cn - 1) > 3) {
        CV_Error(CV_BadNumChannels, "");
    }

    if (mat != header) {
        int hdr_refcount = header->hdr_refcount;
        *header = *mat;
        header->refcount = 0;
        header->hdr_refcount = hdr_refcount;
    }

    total_width = mat->cols * CV_MAT_CN(mat->type);

    if ((new_cn > total_width || total_width % new_cn != 0) && new_rows == 0) {
        new_rows = mat->rows * total_width / new_cn;
    }

    if (new_rows == 0 || new_rows == mat->rows) {
        header->rows = mat->rows;
        header->step = mat->step;
    } else {
        int total_size = total_width * mat->rows;
        if (!CV_IS_MAT_CONT(mat->type))
            CV_Error(CV_BadStep,
                     "The matrix is not continuous, thus its number of rows can not be changed");

        if ((unsigned)new_rows > (unsigned)total_size) {
            CV_Error(CV_StsOutOfRange, "Bad new number of rows");
        }

        total_width = total_size / new_rows;

        if (total_width* new_rows != total_size)
            CV_Error(CV_StsBadArg, "The total number of matrix elements "
                     "is not divisible by the new number of rows");

        header->rows = new_rows;
        header->step = total_width * CV_ELEM_SIZE1(mat->type);
    }

    new_width = total_width / new_cn;

    if (new_width* new_cn != total_width)
        CV_Error(CV_BadNumChannels,
                 "The total width is not divisible by the new number of channels");

    header->cols = new_width;
    header->type = (mat->type  & ~CV_MAT_TYPE_MASK) | CV_MAKETYPE(mat->type, new_cn);

    result = header;
    return  result;
}


// convert array (CvMat or IplImage) to IplImage
CV_IMPL IplImage*
cvGetImage(const CvArr* array, IplImage* img) {
    IplImage* result = 0;
    const IplImage* src = (const IplImage*)array;
    int depth;

    if (!img) {
        CV_Error(CV_StsNullPtr, "");
    }

    if (!CV_IS_IMAGE_HDR(src)) {
        const CvMat* mat = (const CvMat*)src;

        if (!CV_IS_MAT_HDR(mat)) {
            CV_Error(CV_StsBadFlag, "");
        }

        if (mat->data.ptr == 0) {
            CV_Error(CV_StsNullPtr, "");
        }

        depth = cvIplDepth(mat->type);

        cvInitImageHeader(img, cvSize(mat->cols, mat->rows),
                          depth, CV_MAT_CN(mat->type));
        cvSetData(img, mat->data.ptr, mat->step);

        result = img;
    } else {
        result = (IplImage*)src;
    }

    return result;
}


/****************************************************************************************\
*                               IplImage-specific functions                              *
\****************************************************************************************/

static IplROI* icvCreateROI(int coi, int xOffset, int yOffset, int width, int height) {
    IplROI* roi = 0;
    if (!CvIPL.createROI) {
        roi = (IplROI*)cvAlloc(sizeof(*roi));

        roi->coi = coi;
        roi->xOffset = xOffset;
        roi->yOffset = yOffset;
        roi->width = width;
        roi->height = height;
    } else {
        roi = CvIPL.createROI(coi, xOffset, yOffset, width, height);
    }

    return roi;
}

static  void
icvGetColorModel(int nchannels, const char** colorModel, const char** channelSeq) {
    static const char* tab[][2] = {
        {"GRAY", "GRAY"},
        {"", ""},
        {"RGB", "BGR"},
        {"RGB", "BGRA"}
    };

    nchannels--;
    *colorModel = *channelSeq = "";

    if ((unsigned)nchannels <= 3) {
        *colorModel = tab[nchannels][0];
        *channelSeq = tab[nchannels][1];
    }
}


// create IplImage header
CV_IMPL IplImage*
cvCreateImageHeader(CvSize size, int depth, int channels) {
    IplImage* img = 0;

    if (!CvIPL.createHeader) {
        img = (IplImage*)cvAlloc(sizeof(*img));
        cvInitImageHeader(img, size, depth, channels, IPL_ORIGIN_TL,
                          CV_DEFAULT_IMAGE_ROW_ALIGN);
    } else {
        const char* colorModel, *channelSeq;

        icvGetColorModel(channels, &colorModel, &channelSeq);

        img = CvIPL.createHeader(channels, 0, depth, (char*)colorModel, (char*)channelSeq,
                                 IPL_DATA_ORDER_PIXEL, IPL_ORIGIN_TL,
                                 CV_DEFAULT_IMAGE_ROW_ALIGN,
                                 size.width, size.height, 0, 0, 0, 0);
    }

    return img;
}


// create IplImage header and allocate underlying data
CV_IMPL IplImage*
cvCreateImage(CvSize size, int depth, int channels) {
    IplImage* img = cvCreateImageHeader(size, depth, channels);
    assert(img);
    cvCreateData(img);

    return img;
}


// initalize IplImage header, allocated by the user
CV_IMPL IplImage*
cvInitImageHeader(IplImage* image, CvSize size, int depth,
                  int channels, int origin, int align) {
    const char* colorModel, *channelSeq;

    if (!image) {
        CV_Error(CV_HeaderIsNull, "null pointer to header");
    }

    memset(image, 0, sizeof(*image));
    image->nSize = sizeof(*image);

    icvGetColorModel(channels, &colorModel, &channelSeq);
    strncpy(image->colorModel, colorModel, 4);
    strncpy(image->channelSeq, channelSeq, 4);

    if (size.width < 0 || size.height < 0) {
        CV_Error(CV_BadROISize, "Bad input roi");
    }

    if ((depth != (int)IPL_DEPTH_1U && depth != (int)IPL_DEPTH_8U &&
            depth != (int)IPL_DEPTH_8S && depth != (int)IPL_DEPTH_16U &&
            depth != (int)IPL_DEPTH_16S && depth != (int)IPL_DEPTH_32S &&
            depth != (int)IPL_DEPTH_32F && depth != (int)IPL_DEPTH_64F) ||
            channels < 0) {
        CV_Error(CV_BadDepth, "Unsupported format");
    }
    if (origin != CV_ORIGIN_BL && origin != CV_ORIGIN_TL) {
        CV_Error(CV_BadOrigin, "Bad input origin");
    }

    if (align != 4 && align != 8) {
        CV_Error(CV_BadAlign, "Bad input align");
    }

    image->width = size.width;
    image->height = size.height;

    if (image->roi) {
        image->roi->coi = 0;
        image->roi->xOffset = image->roi->yOffset = 0;
        image->roi->width = size.width;
        image->roi->height = size.height;
    }

    image->nChannels = MAX(channels, 1);
    image->depth = depth;
    image->align = align;
    image->widthStep = (((image->width * image->nChannels *
                          (image->depth & ~IPL_DEPTH_SIGN) + 7) / 8) + align - 1) & (~(align - 1));
    image->origin = origin;
    image->imageSize = image->widthStep * image->height;

    return image;
}


CV_IMPL void
cvReleaseImageHeader(IplImage** image) {
    if (!image) {
        CV_Error(CV_StsNullPtr, "");
    }

    if (*image) {
        IplImage* img = *image;
        *image = 0;

        if (!CvIPL.deallocate) {
            cvFree(&img->roi);
            cvFree(&img);
        } else {
            CvIPL.deallocate(img, IPL_IMAGE_HEADER | IPL_IMAGE_ROI);
        }
    }
}


CV_IMPL void
cvReleaseImage(IplImage** image) {
    if (!image) {
        CV_Error(CV_StsNullPtr, "");
    }

    if (*image) {
        IplImage* img = *image;
        *image = 0;

        cvReleaseData(img);
        cvReleaseImageHeader(&img);
    }
}


CV_IMPL void
cvSetImageROI(IplImage* image, CvRect rect) {
    if (!image) {
        CV_Error(CV_HeaderIsNull, "");
    }

    // allow zero ROI width or height
    CV_Assert(rect.width >= 0 && rect.height >= 0 &&
              rect.x < image->width && rect.y < image->height &&
              rect.x + rect.width >= (int)(rect.width > 0) &&
              rect.y + rect.height >= (int)(rect.height > 0));

    rect.width += rect.x;
    rect.height += rect.y;

    rect.x = std::max(rect.x, 0);
    rect.y = std::max(rect.y, 0);
    rect.width = std::min(rect.width, image->width);
    rect.height = std::min(rect.height, image->height);

    rect.width -= rect.x;
    rect.height -= rect.y;

    if (image->roi) {
        image->roi->xOffset = rect.x;
        image->roi->yOffset = rect.y;
        image->roi->width = rect.width;
        image->roi->height = rect.height;
    } else {
        image->roi = icvCreateROI(0, rect.x, rect.y, rect.width, rect.height);
    }
}


CV_IMPL void
cvResetImageROI(IplImage* image) {
    if (!image) {
        CV_Error(CV_HeaderIsNull, "");
    }

    if (image->roi) {
        if (!CvIPL.deallocate) {
            cvFree(&image->roi);
        } else {
            CvIPL.deallocate(image, IPL_IMAGE_ROI);
            image->roi = 0;
        }
    }
}


CV_IMPL CvRect
cvGetImageROI(const IplImage* img) {
    CvRect rect = { 0, 0, 0, 0 };
    if (!img) {
        CV_Error(CV_StsNullPtr, "Null pointer to image");
    }

    if (img->roi)
        rect = cvRect(img->roi->xOffset, img->roi->yOffset,
                      img->roi->width, img->roi->height);
    else {
        rect = cvRect(0, 0, img->width, img->height);
    }

    return rect;
}


CV_IMPL void
cvSetImageCOI(IplImage* image, int coi) {
    if (!image) {
        CV_Error(CV_HeaderIsNull, "");
    }

    if ((unsigned)coi > (unsigned)(image->nChannels)) {
        CV_Error(CV_BadCOI, "");
    }

    if (image->roi || coi != 0) {
        if (image->roi) {
            image->roi->coi = coi;
        } else {
            image->roi = icvCreateROI(coi, 0, 0, image->width, image->height);
        }
    }
}


CV_IMPL int
cvGetImageCOI(const IplImage* image) {
    if (!image) {
        CV_Error(CV_HeaderIsNull, "");
    }

    return image->roi ? image->roi->coi : 0;
}


CV_IMPL IplImage*
cvCloneImage(const IplImage* src) {
    IplImage* dst = 0;

    if (!CV_IS_IMAGE_HDR(src)) {
        CV_Error(CV_StsBadArg, "Bad image header");
    }

    if (!CvIPL.cloneImage) {
        dst = (IplImage*)cvAlloc(sizeof(*dst));

        memcpy(dst, src, sizeof(*src));
        dst->imageData = dst->imageDataOrigin = 0;
        dst->roi = 0;

        if (src->roi) {
            dst->roi = icvCreateROI(src->roi->coi, src->roi->xOffset,
                                    src->roi->yOffset, src->roi->width, src->roi->height);
        }

        if (src->imageData) {
            int size = src->imageSize;
            cvCreateData(dst);
            memcpy(dst->imageData, src->imageData, size);
        }
    } else {
        dst = CvIPL.cloneImage(src);
    }

    return dst;
}


/****************************************************************************************\
*                            Additional operations on CvTermCriteria                     *
\****************************************************************************************/

CV_IMPL CvTermCriteria
cvCheckTermCriteria(CvTermCriteria criteria, double default_eps,
                    int default_max_iters) {
    CvTermCriteria crit;

    crit.type = CV_TERMCRIT_ITER | CV_TERMCRIT_EPS;
    crit.max_iter = default_max_iters;
    crit.epsilon = (float)default_eps;

    if ((criteria.type & ~(CV_TERMCRIT_EPS | CV_TERMCRIT_ITER)) != 0)
        CV_Error(CV_StsBadArg,
                 "Unknown type of term criteria");

    if ((criteria.type & CV_TERMCRIT_ITER) != 0) {
        if (criteria.max_iter <= 0)
            CV_Error(CV_StsBadArg,
                     "Iterations flag is set and maximum number of iterations is <= 0");
        crit.max_iter = criteria.max_iter;
    }

    if ((criteria.type & CV_TERMCRIT_EPS) != 0) {
        if (criteria.epsilon < 0) {
            CV_Error(CV_StsBadArg, "Accuracy flag is set and epsilon is < 0");
        }

        crit.epsilon = criteria.epsilon;
    }

    if ((criteria.type & (CV_TERMCRIT_EPS | CV_TERMCRIT_ITER)) == 0)
        CV_Error(CV_StsBadArg,
                 "Neither accuracy nor maximum iterations "
                 "number flags are set in criteria type");

    crit.epsilon = (float)MAX(0, crit.epsilon);
    crit.max_iter = MAX(1, crit.max_iter);

    return crit;
}

namespace cv {

template<> void Ptr<CvMat>::delete_obj()
{ cvReleaseMat(&obj); }

template<> void Ptr<IplImage>::delete_obj()
{ cvReleaseImage(&obj); }

template<> void Ptr<CvMatND>::delete_obj()
{ cvReleaseMatND(&obj); }

template<> void Ptr<CvSparseMat>::delete_obj()
{ cvReleaseSparseMat(&obj); }

template<> void Ptr<CvMemStorage>::delete_obj()
{ cvReleaseMemStorage(&obj); }

template<> void Ptr<CvFileStorage>::delete_obj()
{ cvReleaseFileStorage(&obj); }

}

/* End of file. */
